1. Field of the Invention
The present invention relates to a simulation device and its method for simulating an operation of an LSI (Large Scale Integrated Circuit) or the other large-scale electronic circuit by processing data in parallel with a plurality of data processing means.
2. Description of the Related Art
A simulation of an electronic circuit with a computer computes and supplies time series change in each potential of several joints and each current value of several elements on the electronic circuit. When executing the simulation, an ordinary differential equation indicating the operation of the electronic circuit is time-discretized, and a simultaneous non-linear equation is obtained by the application of the implicit integration formula to it. The Newton iteration method is applied to the obtained simultaneous non-linear equation, and the resultant solution of a simultaneous linear equation is repeated so to obtain a solution at each discrete time point.
When performing a simulation of a large-scale electronic circuit having more than ten thousands of elements like an LSI, the time required for solving the above simultaneous linear equation occupies more than half the entire calculation time, and is increased with increasing scale of an electronic circuit. A method of solving a simultaneous linear equation includes a direct method and an iteration method. The direct method is not practical because the time required for solving a simultaneous linear equation becomes extremely long as the size of the circuit is increased, and therefore, the iteration method is generally adopted for a simulation of a large-scale electronic circuit.
The iteration method means the way in which an approximation sequence of a solution {x(0), x(1), x(2), . . . } is sequentially solved, so as to arrive at a solution x(i) at full convergence. As the conventional iteration method for use in this kind of simulation, there are, for example, BiCG method (Bi Conjugate Gradient Method), QMR method (Quasi-Minimal Residual Method), CGS method (Conjugate Gradient Squared Method), and Bi-CGSTAB method (Bi-CG Stabilized Method). When actually executing this kind of iteration method, generally performed is the preprocessing for changing a simultaneous equation into a form of getting easy convergence. Without preprocessing, operation will not converge on a solution in some cases, and therefore, preprocessing is practically indispensable.
As preprocessing, an incomplete LU factorization (Lower/Upper factorization) (hereinafter, referred to as ILU factorization) is used in many cases. In the ILU factorization, approximate value of the LU factorization is solved by completely ignoring fills-in generated by the LU factorization, or by allowing the fills-in to be propagated to a constant level. A fill-in means an element that is "0" in the matrix before the LU factorization and no longer "0" after the LU factorization. The processing for allowing the propagation of such fill-in to a constant level L is expressed as ILU(L) and the processing thereof is to be executed like the flow chart of FIG. 12.
When executing the ILU factorization-preprocessed iteration method as mentioned above by use of a parallel processor, a circuit is partitioned at first, thereby to get a bordered-block-diagonal matrix as a coefficient matrix, as illustrated in FIG. 13. The ILU factorization on this coefficient matrix is executed in parallel in every block of A1, A2, . . . , An, respectively by a plurality of processors, and thereafter, the ILU factorization on the combined portion D is sequentially executed.
A method for solving the problem caused by the ILU factorization on the combined portion D being a sequential execution, is disclosed in the introduction "A Parallel Block-Diagonal Preconditioned Conjugate-Gradient Solution Algorithm for Circuit and Device Simulations" of "International Conference on Computer Aided Design 90". The same article discloses a method of performing the ILU factorization on the whole blocks and combined portion in parallel by ignoring the non-diagonal blocks B1 to Bn, and C1 to Cn in the bordered portion.
According to the above-mentioned various methods, an operation of an electronic circuit can be simulated by parallel processing of a plurality of data processing means. However, according to the first method of the conventional technique, in which the ILU factorization on the combined portion is subject to a sequential execution at the end, it is difficult to shorten the whole processing time. This is why, although it may be possible to shorten the processing time by increasing the number of processors for parallel processing of the ILU factorization in every block and decreasing the volume of each processing, the number of the ILU factorization sequentially executed on the combined portion at the end is increased, thereby increasing the processing time of the combined portion sequentially executed. For example, the conventional simulation disclosed in the above article, if using four processors, improves the speed about 2.2 times faster than the case of using one processor.
The second method of the conventional technique, in which the ILU factorization on the whole blocks and combined portion is performed in parallel by ignoring non-diagonal blocks of the bordered portion in the parallel processing of the ILU factorization, increases the iteration times for a solution of a linear equation to some times by the influence of the ignored portion, thereby preventing from shortening the whole processing time. This is why, although in the ILU factorization, the iteration times becomes less according as the result is closer to a complete LU factorization, ignorance of non-diagonal blocks in the bordered portion results in an increase in the difference between the ILU factorization and the complete LU factorization.
Further, in the second method of the conventional technique, since the error of the numerical operation such as roundoff error is increased if the iteration times is increased, a linear equation may not converge on a solution in the actual calculation however it may be an iteration method capable of converging theoretically.